home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / compress / string.c.z / string.c
C/C++ Source or Header  |  1997-09-09  |  8KB  |  280 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. /*
  4.  * string.c:    String table manipulation routines. Can be used to compute
  5.  *        the dictionary as well as uncompress files.
  6.  */
  7.  
  8. #include "defs.h"
  9.  
  10. extern int MAX_WORDS;
  11. extern int RESERVED_CHARS;
  12.  
  13. int next_free_strtable = 0;
  14. char *free_strtable = NULL; /*[DEF_MAX_WORDS * AVG_WORD_LEN]; */
  15.  
  16. extern int usemalloc;
  17.  
  18. /* debugging only */
  19. int
  20. dump_string(string_table, string_file, index_file)
  21.     char    **string_table;
  22.     unsigned char    *string_file, *index_file;
  23. {
  24.     FILE    *stringfp;
  25.     FILE    *indexfp;
  26.     int    i;
  27.  
  28.     if ((stringfp = fopen(string_file, "w")) == NULL) {
  29.         fprintf(stderr, "cannot open for writing: %s\n", string_file);
  30.         return 0;
  31.     }
  32.     if ((indexfp = fopen(index_file, "r")) == NULL) {
  33.         fprintf(stderr, "cannot open for reading: %s\n", index_file);
  34.         fclose(stringfp);
  35.         return 0;
  36.     }
  37.  
  38.     for(i=0; i<MAX_WORDS; i++) fprintf(stringfp, "%s\n", string_table[i]);
  39.  
  40.     fflush(stringfp);
  41.     fclose(stringfp);
  42.     fclose(indexfp);
  43.     return 1;
  44. }
  45.  
  46. /*
  47.  * VERY particular to the format of the string-table file: which is a series
  48.  * of words separated by newlines -- this does an fscanf+strlen in one scan.
  49.  */
  50. int
  51. mystringread(fp, str)
  52.     FILE    *fp;
  53.     char    *str;
  54. {
  55.     int    numread = 0;
  56.     int    c;
  57.  
  58.     while((numread <= MAX_WORD_LEN) && ((c = getc(fp)) != EOF)) {
  59.         if (c == '\n') {
  60.             if (numread==0) break;    /* first char '\n' => in padded area */
  61.             c = '\0';
  62.             str[numread++] = c;
  63.             return numread;
  64.         }
  65.         else str[numread++] = c;
  66.     }
  67.     str[numread] = '\0';
  68.     if (c == EOF) return -1;
  69.     return numread;
  70. }
  71.  
  72. int
  73. build_string(string_table, stringfp, bytestoread, initialwordindex)
  74.     char    *string_table[DEF_MAX_WORDS]; /*[MAX_WORD_LEN+2]; */
  75.     FILE    *stringfp;
  76.     int    bytestoread;
  77.     int    initialwordindex;
  78. {
  79.     int    wordindex = initialwordindex;
  80.     int    numread = 0;
  81.     int    ret;
  82.     char    dummybuf[MAX_WORD_BUF];
  83.     char    *word;
  84.  
  85.     if (bytestoread == -1) {    /* read until end of file */
  86.         while (wordindex < MAX_WORDS) {
  87.             if (usemalloc) word = dummybuf;
  88.             else {
  89.                 if (free_strtable == NULL) free_strtable = (char *)malloc(AVG_WORD_LEN * DEF_MAX_WORDS);
  90.                 if (free_strtable == NULL) break;
  91.                 word = &free_strtable[next_free_strtable];
  92.             }
  93.             if ((ret = mystringread(stringfp, word)) == 0) continue;
  94.             if (ret == -1) break;
  95.             if (usemalloc) {
  96.                 if ((word = (char *)malloc(ret + 2)) == NULL) break;
  97.                 strcpy(word, dummybuf);
  98.             }
  99.             else next_free_strtable += ret + 2;
  100.             string_table[wordindex] = word;
  101. #if    0
  102.             printf("word=%s index=%d\n", string_table[wordindex], wordindex);
  103. #endif    /*0*/
  104.             wordindex ++;
  105.         }
  106.     }
  107.     else {    /* read only the specified number of bytes */
  108.         while((wordindex < MAX_WORDS) && (bytestoread > numread)) {
  109.             if (usemalloc) word = dummybuf;
  110.             else {
  111.                 if (free_strtable == NULL) free_strtable = (char *)malloc(AVG_WORD_LEN * DEF_MAX_WORDS);
  112.                 if (free_strtable == NULL) break;
  113.                 word = &free_strtable[next_free_strtable];
  114.             }
  115.             if ((ret = mystringread(stringfp, word)) <= 0) break;    /* quit if EOF OR if padded area */
  116.             if (usemalloc) {
  117.                 if ((word = (char *)malloc(ret + 2)) == NULL) break;
  118.                 strcpy(word, dummybuf);
  119.             }
  120.             else next_free_strtable += ret + 2;
  121.             string_table[wordindex] = word;
  122. #if    0
  123.             printf("word=%s index=%d\n", string_table[wordindex], wordindex);
  124. #endif    /*0*/
  125.             wordindex ++;
  126.             numread += ret;
  127.         }
  128.     }
  129.     return wordindex;
  130. }
  131.  
  132. /*
  133.  * Interprets srcbuf as a set of srclen/2 short integers. It looks for all the
  134.  * short-integers encoding words in the matched line and loads only those blocks
  135.  * of the string table. Note: srcbuf must be aligned on a short-int boundary.
  136.  */
  137. int
  138. build_partial_string(string_table, stringfp, srcbuf, srclen, linebuf, linelen, blocksize, loaded_string_table)
  139.     char    *string_table[DEF_MAX_WORDS]; /* [MAX_WORD_LEN+2]; */
  140.     FILE    *stringfp;
  141.     unsigned char    *srcbuf;
  142.     int    srclen;
  143.     unsigned char    *linebuf;
  144.     int    linelen;
  145.     int    blocksize;
  146.     char    loaded_string_table[STRING_FILE_BLOCKS];
  147. {
  148.     unsigned char    *srcpos;
  149.     int        blockindex = 0;
  150.     unsigned short    srcinit, srcend;
  151.     unsigned short    wordnums[MAX_NAME_LEN];    /* maximum pattern length */
  152.     int    numwordnums = 0;
  153.     int    i;
  154.  
  155.     /*
  156.      * Find all the relevant wordnums in the line.
  157.      */
  158.     i = 0;
  159.     while(i<linelen) {
  160.         if (linebuf[i] < RESERVED_CHARS) {
  161.             if (linebuf[i] == BEGIN_VERBATIM) {
  162.                 if (ISASCII(linebuf[i+1])) {
  163.                     while ((linebuf[i] != END_VERBATIM) && (i <linelen)) i ++;
  164.                 }
  165.                 else i ++;    /* skip over the BEGIN_VERBATIM of non-ascii character */
  166.                 i ++;        /* skip over the non-ascii character OR END_VERBATIM: let it overshoot linelen...its ok */
  167.             }
  168.             else i ++;        /* skip over the character encoding a special word OR a special character */
  169.         }
  170.         else {
  171.             wordnums[numwordnums] = (unsigned char)linebuf[i];        /* always big-endian compression */
  172.             wordnums[numwordnums] <<= 8;
  173.             wordnums[numwordnums] |= (unsigned char)linebuf[i+1];
  174.             wordnums[numwordnums] = decode_index(wordnums[numwordnums]);    /* roundabout to avoid buserr */
  175.             numwordnums ++;
  176.             i += sizeof(short);
  177.         }
  178.     }
  179.  
  180. #if    0
  181.     for (i=0; i<numwordnums; i++) printf("num%d=%d\n", i, wordnums[i]);
  182.     getchar();
  183. #endif    /*0*/
  184.  
  185.     srcpos = srcbuf;
  186.     srcend = *((unsigned short *)srcpos);
  187.     srcpos += sizeof(short);
  188.     while (srcpos < srcbuf + srclen) {
  189.         srcinit = srcend;
  190.         srcend = *((unsigned short *)srcpos);
  191.         srcpos += sizeof(short);
  192. #if    0
  193.         printf("%d -- %d\n", srcinit, srcend);
  194. #endif    /*0*/
  195.         for (i=0; i<numwordnums; i++)
  196.             if ((wordnums[i] >= srcinit) && (wordnums[i] <= srcend)) goto include_page;
  197.  
  198.         blockindex++;
  199.         continue;
  200.  
  201.     include_page:    /* Include it if any of the word-indices fit within this range */
  202.         if (loaded_string_table[blockindex++]) continue;
  203. #if    0
  204.         printf("build_partial_string: hashing words in page# %d\n", blockindex);
  205. #endif    /*0*/
  206.         loaded_string_table[blockindex - 1] = 1;
  207.         fseek(stringfp, (blockindex-1)*blocksize, 0);
  208.         build_string(string_table, stringfp, blocksize, srcinit);
  209.     }
  210.     return 0;
  211. }
  212.  
  213. pad_string_file(filename, FILEBLOCKSIZE)
  214.     unsigned char *filename;
  215.     int FILEBLOCKSIZE;
  216. {
  217.     FILE    *outfp, *infp, *indexfp;
  218.     int    offset = 0, len;
  219.     unsigned char buf[MAX_NAME_LEN];
  220.     int    pid = getpid();
  221.     int    i;
  222.     unsigned short    wordindex = 0;
  223.  
  224.     if ((infp = fopen(filename, "r")) == NULL) {
  225.         fprintf(stderr, "cannot open for reading: %s\n", filename);
  226.         exit(2);
  227.     }
  228.     sprintf(buf, "%s.index", filename);
  229.     if ((indexfp = fopen(buf, "w")) == NULL) {
  230.         fprintf(stderr, "cannot open for writing: %s\n", buf);
  231.         fclose(infp);
  232.         exit(2);
  233.     }
  234.     sprintf(buf, "%s.%d", filename, pid);
  235.     if ((outfp = fopen(buf, "w")) == NULL) {
  236.         fprintf(stderr, "cannot open for writing: %s\n", buf);
  237.         fclose(infp);
  238.         fclose(indexfp);
  239.         exit(2);
  240.     }
  241.     if ((FILEBLOCKSIZE % MIN_BLOCKSIZE) != 0) {
  242.         fprintf(stderr, "invalid block size %d: changing to %d\n", FILEBLOCKSIZE, MIN_BLOCKSIZE);
  243.         FILEBLOCKSIZE = MIN_BLOCKSIZE;
  244.     }
  245.     fprintf(indexfp, "%d\n", FILEBLOCKSIZE);
  246.  
  247.     buf[0] = '\0';
  248.     if ((char *)buf != fgets(buf, MAX_NAME_LEN, infp)) goto end_of_input;
  249.     len = strlen((char *)buf);
  250.     fputs(buf, outfp);
  251.     fprintf(indexfp, "%d\n", wordindex);
  252.     offset += len;
  253.     wordindex ++;
  254.  
  255.     while(fgets(buf, MAX_NAME_LEN, infp) == (char *)buf) {
  256.         len = strlen((char *)buf);
  257.         if (offset + len > FILEBLOCKSIZE) {
  258.             for (i=0; i<FILEBLOCKSIZE-offset; i++)    /* fill up with so many newlines until the next block size */
  259.                 putc('\n', outfp);
  260.             fputs(buf, outfp);
  261.             fprintf(indexfp, "%d\n", wordindex);
  262.             offset = 0;
  263.         }
  264.         else fputs(buf, outfp);
  265.         offset += len;
  266.         wordindex ++;
  267.     }
  268.     fprintf(indexfp, "%d\n", wordindex);
  269.  
  270. end_of_input:
  271.     fclose(infp);
  272.     fflush(outfp);
  273.     fclose(outfp);
  274.     fflush(indexfp);
  275.     fclose(indexfp);
  276.     sprintf(buf, "mv %s.%d %s\n", filename, pid, filename);
  277.     system(buf);
  278.     return 0;
  279. }
  280.